Информационные модели на графах

Граф — это средство для наглядного представления состава и структуры системы.

Для того, чтобы представить информацию о составе и структуре системы графически, необходимо в виде чертежа изобразить компоненты системы и соединить их между собой линиями. Пример: структура молекулы воды (компоненты системы – атомы соединены между собой линиями)

Элементы графа: Вершины — это компоненты системы изображаемые кругами, овалами, прямоугольниками. Ребра — это линии (стрелки), связывающие компоненты между собой определенным образом.

Структуры графа: 1) линейный – вершины соединены последовательно (схема Екатеринбургского метро, схема состава поезда) 1 2 3

2) дерево —граф, предназначенный для отображения подчиненности между объектами. Каждая вершина связана только с верхней и не связана больше ни с чем (цепная реакция, генеалогическое дерево);

3) сеть — это граф, в котором вершины связаны между собой по принципу «многие ко многим» (компьютерная сеть);

4) блок-схема — это граф, отображающий последовательность выполнения действий. Его вершины отображают отдельные действия и изображаются геометрическими фигурами (алгоритм).

Теория графов и Леонард Эйлер Загадка о 7 мостах через реку Преголь (Кёнигсберг). В XVIII веке задача заинтересовала математика Леонарда Эйлера и он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

Выводы Эйлера: 1) Число нечётных вершин (к которым ведёт нечётное число рёбер) графа должно быть чётно (нет графа, который имел бы нечётное число нечётных вершин). 2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф (можно начинать с любой вершины и завершить граф в той же вершине). 3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Созданная Эйлером, при решении загадки, теория графов нашла широкое применение в транспортных системах (составление оптимальных маршрутов доставки грузов), экономике, банковской сфере, химии, медицине, криминалистике и т.д. и т.п.).